package data;

import java.util.Objects;
import java.util.Random;

/**
 * 跳表
 * @author Tang Jiujia
 * @since 15:43 2020-04-14
 */
public class SkipList {

    /**
    * 索引的最大层数
    * */
    private static final int MAX_LEVEL = 16;
    /**
    * 当前节点索引总层数
    * */
    private int levelCount = 1;
    /**
    * 链表头节点
    * */
    private Node head = new Node(MAX_LEVEL);
    private Random random = new Random();

    /**
     * 向链表中插入值value
     *
     * @param value 要插入的值
     */
    public void insert(int value) {
        //选择所插入的层数
        int level = head.nextNodes[0] == null ? 1 : randomLevel();
        //保证每次最多增加一层
        if (level > levelCount) {
            level = ++levelCount;
        }
        Node newNode = new Node(level);
        newNode.data = value;
        Node[] update = new Node[level];
        for (int i = 0; i < level; ++i) {
            update[i] = head;
        }

        Node p = head;
        //从头节点开始，查找新value的插入位置
        for (int i = levelCount - 1; i >= 0; --i) {
            //当后面一个节点的值大等于插入value时，当前节点就是插入点
            while (p.nextNodes[i] != null && p.nextNodes[i].data < value) {
                p = p.nextNodes[i];
            }
            //插入的node level 必须大于i
            if (level > i) {
                update[i] = p;
            }
        }
        //更新node next
        for (int i = 0; i < level; i++) {
            newNode.nextNodes[i] = update[i].nextNodes[i];
            update[i].nextNodes[i] = newNode;
        }
    }

    /**
     * 用于随机索引层次，如果是奇数+1，防止伪随机。
     *
     * @return int
     */
    private int randomLevel() {
        int level = 1;
        for (int i = 1; i < MAX_LEVEL; ++i) {
            if (random.nextInt() % 2 == 1) {
                level++;
            }
        }
        return level;
    }

    /**
     * 查找值为value的节点
     *
     * @param value	要查找的值
     * @return data.SkipList.Node
     */
    public Node find(int value) {
        Node node = head;
        for (int i= levelCount - 1; i >=0; i--) {
            while (node.nextNodes[i] != null && node.nextNodes[i].data < value) {
                node = node.nextNodes[i];
            }
        }
        Node result = node.nextNodes[0];
        if (result != null && result.data == value) {
            return result;
        }
        return null;
    }

    /**
     * 删除指定值所在节点
     *
     * @param value
     */
    public void delete(int value) {
        Node[] update = new Node[levelCount];
        Node p = head;
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.nextNodes[i] != null && p.nextNodes[i].data < value) {
                p = p.nextNodes[i];
            }
            update[i] = p;
        }
        if (p.nextNodes[0] != null && p.nextNodes[0].data == value) {
            for (int i = levelCount - 1; i >= 0; --i) {
                if (update[i].nextNodes[i] != null && update[i].nextNodes[i].data == value) {
                    update[i].nextNodes[i] = update[i].nextNodes[i].nextNodes[i];
                }
            }
        }
    }

    /**
    * 代表一个节点，记录了节点数据及其下一个节点
    * */
    private static class Node {
        /**
        * 当前节点存储的数据
        * */
        private int data = -1;

        /**
        * 下一节点及其所有索引组成的数组,比如nextNodes[3],表示当前节点在第三层的下一个节点
        * */
        private Node[] nextNodes;
        /**
        * 当前节点索引层数
        * */
        private int currentLevel = 0;

        public Node(int level) {
            nextNodes = new Node[level];
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", currentLevel=" + currentLevel +
                    '}';
        }
    }

    public static SkipList newInstant(int[] arr) {
        Objects.requireNonNull(arr);
        if (arr.length < 1) {
            throw new RuntimeException("请传入用于初始化的数组！");
        }
        SkipList skipList = new SkipList();
        int len = arr.length;
        Node p = skipList.head;
        for (int i = 0; i < len; i++) {
            if (p !=null) {
                p.data = arr[i];
                p.nextNodes[0] = new Node(MAX_LEVEL);
                p = p.nextNodes[0];
            }
        }
        return skipList;
    }

    public void printAll() {
        Node p = head;
        Node[] c = p.nextNodes;
        Node[] d = c;
        int maxLevel = c.length;
        for (int i = maxLevel - 1; i >= 0; i--) {
            do {
                System.out.print((d[i] != null ? d[i].data : null) + ":" + i + "-------");
            } while (d[i] != null && (d = d[i].nextNodes)[i] != null && d[i].data > 0);
            System.out.println();
            d = c;
        }
    }

    public static void main(String[] args) {
        int[] arr = { 2, 4, 7, 9, 13, 16, 19, 20, 23};
        SkipList skipList = SkipList.newInstant(arr);
        skipList.insert(5);
        skipList.insert(22);
        skipList.insert(17);
        skipList.insert(3);
        skipList.printAll();
    }
}
